#!/usr/bin/perl
# 
use strict;
use warnings;

my $text = <<END;
# Exercise 12.1
# 
# Basic string matching. Write a program that looks for a query string in a target 
# string. For instance, if the query string is "gone", it finds a match at position 22 of 
# the target string "goof through the way-gone-osphere." Don't use regular expres-
# sions or any of Perl's built-in string-matching abilities; instead, examine individual 
# positions in the strings, compare characters, and invent your own algorithm.
#
# Answer to Exercise 12.1
#
# You could do this in several different ways.  We're going to show a method that uses
# the "substr" built-in function to examine individual characters, and does a very
# straightforward algorithm.  If it finds the first character of the query string, it
# looks for the second character; and so on.
#
# By the way, "goof through the way-gone-osphere" is a quote from comedian Lord Buckley's
# "The Hip Einie", a life of Albert Einstein.
END

my $query = 'gone';

my $qlen = length($query);

my $tlen = length($text);

# $t is the position in the text
# $q is the position in the query

my $t = 0;

# loop through the positions in the text
# LOOP: is a statement label for use by the "next" statement.
LOOP:while($t < $tlen - $qlen + 1)  {

	# loop through the positions in the query
	for(my $q = 0 ; $q < $qlen ; ++$q ) {

		# Compare the characters in the query and in the text
		if(substr($query, $q, 1) ne substr($text, $t + $q, 1)) {
			++$t;
			next LOOP;
		}
	}

	# If we get here, we've matched every character in the query

	print "Found match at position ", $t + 1, "\n";
	print "query = $query   matched string = ", substr($text, $t, $qlen), "\n";
	last;
}

exit;
